package com.algrithom.bfs;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 847. 访问所有节点的最短路径
 * 
 * @author think
 */
public class Solution2 {
    
    public static void main(String[] args){
        int[][] graph = new int[][]{{1,2,3},{0},{0},{0}};
        Solution2 solution2 = new Solution2();
        System.out.println(solution2.shortestPathLength(graph));
    }
    
    public int shortestPathLength(int[][] graph){
        int rowLen = graph.length;
        boolean[][] visited = new boolean[rowLen][1 << rowLen];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < rowLen; i++) {
            queue.add(new int[]{i,1 << i});
        }
        int step = 0;
        int endState = (1 << rowLen) - 1;
        while (!queue.isEmpty()) {
            step++;
            for (int i = queue.size(); i > 0; i--) {
                if (Objects.isNull(queue.peek())) {
                    continue;
                }
                int[] array = queue.poll();
                int state = array[1];
                int point = array[0];
                for (int next : graph[point]) {
                    int nextState = state | (1 << next);
                    if (nextState == endState) {
                        return step;
                    }
                    if (visited[next][nextState]) {
                        continue;
                    }
                    visited[next][nextState] = true;
                    queue.add(new int[]{next,nextState});
                }
            }
        }
        return 0;
    }
    
    public int shortestPathLength2(int[][] graph){
        int n = graph.length;
        int mask = 1 << n;
        
        // Floyd 求两点的最短路径
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) {
                dist[i][j] = 1;
            }
        }
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j],dist[i][k] + dist[k][j]);
                }
            }
        }
        
        // DP 过程，如果从 i 能够到 j 的话，使用 i 到 j 的最短距离（步长）来转移
        int[][] f = new int[mask][n];
        // 起始时，让所有状态的最短距离（步长）为正无穷
        for (int i = 0; i < mask; i++) {
            Arrays.fill(f[i],Integer.MAX_VALUE);
        }
        // 由于可以将任意点作为起点出发，可以将这些起点的最短距离（步长）设置为 0
        for (int i = 0; i < n; i++) {
            f[1 << i][i] = 0;
        }
        
        // 枚举所有的 state
        for (int state = 0; state < mask; state++) {
            // 枚举 state 中已经被访问过的点
            for (int i = 0; i < n; i++) {
                if (((state >> i) & 1) == 0) {
                    continue;
                }
                // 枚举 state 中尚未被访问过的点
                for (int j = 0; j < n; j++) {
                    if (((state >> j) & 1) == 1) {
                        continue;
                    }
                    f[state | (1 << j)][j] = Math.min(f[state | (1 << j)][j],f[state][i] + dist[i][j]);
                }
            }
        }
        
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.min(ans,f[mask - 1][i]);
        }
        return ans;
    }
}